AtCoder Beginner Contest 345 A-F 题解

AtCoder Beginner Contest 345

A - Leftrightarrow

Question

给你一个由 <、= 和 > 组成的字符串 $S$ 。

请判断 $S$ 是否是双向箭头字符串。

字符串 $S$ 是双向箭头字符串，当且仅当存在一个正整数 $k$ ，使得 $S$ 是一个 <、 $k$ 个 = 和一个 >的连接，且顺序如此，长度为 $(k + 2)$ 。

Solution

按照题意模拟

Code

#include <bits/stdc++.h>
using namespace std;
int main() {
    string s;
    cin >> s;
    if (s[0] != '<') {printf("No\n"); return 0;}
    if (s.back() != '>') {printf("No\n"); return 0;}
    for (int i = 1; i < s.size() - 1; i++) {
        if (s[i] != '=') {printf("No\n"); return 0;}
    }
    printf("Yes\n");
}

B - Integer Division Returns

Quesiton

给定一个介于 $- 10^{18}$ 和 $10^{18}$ 之间的整数 $X$ ，打印 $⌈ \frac{X}{10} ⌉$ 。
这里， $⌈ a ⌉$ 表示不小于 $a$ 的最小整数。

Solution

分类讨论，如果 $a$ 能整除 $10$ ，那么答案就是 $\frac{a}{10}$

如果 $a$ 是正数，输出 $⌊ \frac{a}{10} ⌋ + 1$
如果 $a$ 是负数，输出 $⌊ \frac{a}{10} ⌋$

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    ll n; cin >> n;
    if (n % 10 == 0) {
        cout << n / 10 << '\n';
    }
    else {
        if (n > 0) {
            cout << n / 10 + 1 << '\n';
        }
        else {
            cout << n / 10 << '\n';
        }
    }
}

C - One Time Swap

Question

给你一个字符串 $S$ 。请找出以下操作 $1$ 次的字符串数。

设 $N$ 是 $S$ 的长度。选择一对整数 $(i, j)$ 使得 $1 \leq i < j \leq N$ 和 $S$ 的 $i$ -th 和 $j$ -th 字符互换。

Solution

考虑交换的对数是 $\frac{n (n + 1)}{2}$

如果一个字母，和之前相同的字母交换，得到的还是原串，否则得到的串是一个新串

所以我们只需要统计每个字符与之前的多少个字母不同就可以得到答案

注意要判断是否能得到原串

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    string s; cin >> s;
    ll n = s.size(); s = " " + s;
    vector<ll> num(26,0);
    ll ans = 0, flg = 0;
    for (int i = 1; i <= n; i++) {
        if (num[s[i] - 'a'] > 0) flg = 1;
        num[s[i] - 'a']++;
        ans += i - num[s[i] - 'a'];
    }
    cout << ans + flg << '\n';
}

D - Tiling

Quesiton

有一个由 $H$ 行和 $W$ 列组成的网格，每个单元格的边长为 $1$ ，我们有 $N$ 块瓷砖。
其中的 $i$ 瓷砖（ $1 \leq i \leq N$ ）是一个大小为 $A_{i} \times B_{i}$ 的矩形。
请判断是否有可能将这些瓷砖放置在网格上，从而满足以下所有条件：

每个单元格都正好被一个图块覆盖。
有未使用的瓦片也没关系。
瓷砖在放置时可以旋转或翻转。但是，每块瓦片必须与单元格的边缘对齐，不得超出网格。

$N \leq 7, H, W \leq 10$

Solution

考虑到 $N, H, W$ 都特别小，直接暴力

直接枚举放瓷砖的顺序以及每块砖是否旋转，最后暴力放砖即可

我在放砖的时候使用了优先队列，所以时间复杂度为 $O (H W \log H W)$

实际上判断放砖可以优化到 $O (H W)$

总时间复杂度就为 $O (N! \cdot 2^{N} \cdot H W)$

Code

#include <bits/stdc++.h>
using namespace std;

typedef vector<vector<int> > vvi;
typedef pair<int, int> pii;


int main() {
    int n; cin >> n;
    int H, W; cin >> H >> W;
    vector<pii> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i].first >> a[i].second;
    }

    auto check = [&]  (vector<int> &id, int S) {
        vector<vector<int> > v(H + 1, vector<int>(W + 1,0));
        priority_queue<pii, vector<pii>, greater<pii> > pq;
        for (int i = 1; i <= H; i++) {
            for (int j = 1; j <= W; j++) {
                pq.push({i,j});
            }
        }
        for (int i = 1; i <= n; i++) {
            auto &[dx, dy] = a[id[i]];
            if (S >> (i - 1) & 1) 
                swap(dx, dy);
            while (!pq.empty() && v[pq.top().first][pq.top().second]) pq.pop();
            if (pq.empty()) {return 1;}
            auto [x, y] = pq.top(); pq.pop();
            for (int i_ = x; i_ < x + dx; i_++) {
                for (int j_ = y; j_ < y + dy; j_++) {
                    if (i_ > H || j_ > W || v[i_][j_] == 1) return 0;
                    v[i_][j_] = 1;
                }
            }
        }
        while (!pq.empty() && v[pq.top().first][pq.top().second]) pq.pop();
        if (pq.empty()) return 1;
        return 0;
    };

    vector<int> id (n + 1);
    iota(id.begin(), id.end(), 0);
    do {
        for (int S = 0; S < (1<<n); S++) 
            if (check(id, S)) {cout << "Yes\n"; return 0;}  
    } while (next_permutation(id.begin() + 1, id.end()));
    cout << "No\n";
    return 0;
}

E - Colorful Subsequence

Question

有 $N$ 个球排成一排。
左边的 $i$ 个球的颜色是 $C_{i}$ ，数值是 $V_{i}$ 。

高桥希望在不改变顺序的情况下，将这一行中的 $K$ 个球移除，这样在排列剩余的球时，就不会有相邻的两个球颜色相同。此外，在此条件下，他希望最大化这一行中剩余球的总价值。

请计算高桥是否能移除 $K$ 个球，使剩下的一行中没有相邻的两个球颜色相同。如果可以，求剩余球的最大总值。

$1 \leq K < N \leq 2 \times 10^{5}$
$K \leq 500$
$1 \leq C_{i} \leq N$
$1 \leq V_{i} \leq 10^{9}$

Solution

先考虑一种朴素的 DP，定义 $d p [i] [j] [c o l]$ 表示前 $i$ 个球，以及移走了 $j$ 个，末尾的最后一个球的颜色为 $c o l$ 的最大值

考虑两种情况：

移走第 $i$ 个球，那么转移方程为 $d p [i] [j] [c o l^{'}] = max {d p [i - 1] [j - 1] [c o l^{'}]}$ ，其中 $c o l^{'}$ 为上一次球的颜色
不移走第 $i$ 个球，那么转移方程为 $d p [i] [j] [c o l] = max {d p [i - 1] [j] [c o l^{'}] + v [i]}, c [i] \neq c o l^{'}$

这样的时间复杂度为 $O (N^{2} K)$ 会超时

观察发现 $d p [i] [j - 1] [c o l]$ 的很多值都是空的，所以考虑值维护其最大值以及和最大值颜色不同的次大值，这样子每次转移肯定能从最大值和次大值里面挑一个转移，后面的小值就不需要去考虑了

所以我们修改一下定义

$d p [i] [j] [p]$ 记录前 $i$ 个球，移走了 $j$ 个，的最大值，次大值的 $v [i]$ 总值和颜色

转移过程和朴素情况一样，只是当最大值和当前的 $c [i]$ 相同时，改用次大值转移

这样的空间复杂度为 $O (N K)$ 会超内存

发现 $d p [i]$ 的状态只与 $d p [i - 1]$ 有关，所以考虑使用滚动数组把空间优化到了 $O (K)$

Code

#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const ll inf = 1e15;

int main() {
    freopen ("E.in", "r", stdin);
    int k ,n; cin >> n >> k;
    vector<int> c(n + 1), v(n + 1);
    for (int i = 1; i <= n; i++) 
        cin >> c[i] >> v[i];
    
    const vector<pll> infv = {{-inf, -1}, {-inf, -2}};
    vector<vector<vector<pll>>> dp(2);  // 三维数组 dp[i][j][col] 表示前 i 个物品中选了 j 个，且最后一个物品的颜色是 col 的最大价值
    dp[0].resize(k + 1, infv); dp[1].resize(k + 1, infv);
    dp[0][0][0].first = dp[0][0][1].first = 0;

    for (int i = 1; i <= n; i++) {
        const int col = c[i], val = v[i];
        auto &cur = dp[i & 1], &pre = dp[(i - 1) & 1];
        for (int j = 0; j <= k; j++)
            cur[j] = infv;
        
        //选了当前物品
        for (int j = 0; j <= k; j++) {
            for (auto &x : pre[j]) {
                const ll preval = x.first, precol = x.second;
                if (precol == col) continue;
                cur[j].push_back({preval + val, col});
                break;
            }
        }
        //没选当前物品
        for (int j = 1; j <= k; j++) {
            for (auto &x : pre[j - 1]) {
                const ll preval = x.first, precol = x.second;
                cur[j].push_back({preval, precol});
            }
        }

        //去重
        for (int j = 0; j <= k; j++) {
            auto &a = cur[j];
            sort(a.begin(), a.end()); reverse(a.begin(), a.end());
            if (a[0].second == a[1].second) {
                ll secval = -inf, seccol = -2;
                for (auto x : a) {
                    if (x.second != a[0].second) {
                        secval = x.first;
                        seccol = x.second;
                        break;
                    }
                }
                a[1] = {secval, seccol};
            }
            a.resize(2);
        }
    }

    ll ans = dp[n & 1][k][0].first;
    cout << (ans < 0 ? -1 : ans) << endl;
    return 0;
}

F - Many Lamps

Question

有一个简单的图，图中有 $N$ 个顶点，编号为 $1$ 至 $N$ ，有 $M$ 条边，编号为 $1$ 至 $M$ 。边 $i$ 连接顶点 $u_{i}$ 和 $v_{i}$ 。

每个顶点上都有一盏灯。初始时，所有的灯都是熄灭的。

请在 $0$ 和 $M$ 之间（包括首尾两次）执行以下操作，以确定是否可以恰好打开 $K$ 盏灯。

选择一条边。假设 $u$ 和 $v$ 是边的端点。切换 $u$ 和 $v$ 上的灯的状态。也就是说，如果灯亮着，则将其关闭，反之亦然。

如果可以恰好打开 $K$ 盏灯，请打印实现该状态的操作序列。

Solution

简化问题，整个图是连通的

有一个性质：开的灯的数量肯定是偶数，证明如下

每次对一条边进行操作：

初始两个灯都是亮的，那么总亮灯数 $- 2$
初始一亮一暗，那么总亮灯数不变
初始两个灯都是灭的，那么总亮灯数 $+ 2$

奇偶性不变，初始是 $0$ 为偶数，所以亮的灯的数量总是偶数

考虑连通图的总数为 $N$ ，设 $X$ 为小于等于 $N$ 的最大偶数，有一种构造方法能让 $X$ 盏灯都点亮

先建立连通图的生成树 $G$
取 $G$ 的一个叶节点 $u$ ，考虑与叶节点连接的其父亲节点 $v$
如果 $u$ 是灭灯状态的话，那么对 $u - v$ 进行一次转换操作，如果 $u$ 是亮灯的话则不操作
删除 $u - v$ 这条边

为什么这样是有效的，因为如果 $u$ 是灭灯

$v$ 也是灭灯，那么同时点亮了两盏灯，能使亮灯数增加
$v$ 是亮灯，虽然亮灯数没有变大，但是能把 $u - v$ 的亮灯状态进行调换，由于叶节点只连接父节点一盏灯，但父节点能连接很多其他灯，把亮的灯放到叶子节点，让父节点更有机会和别的节点进行亮两盏灯的操作

如果 $K < X$ ，亮灯的过程是从 $0 \sim X$ 的连续偶数，当亮灯数 $= X$ 时，中止过程即可

Code

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
int main() {
    freopen ("F.in", "r", stdin);
    int n, m, k; cin >> n >> m >> k;
    vector<vector<pii> > g(n + 1);
    for (int i = 1; i <= m; i++) {
        int u,v; cin >> u >> v;
        g[u].push_back({v, i});
        g[v].push_back({u, i});
    }

    int Y = 0;
    vector<int> ans, vis(n + 1, 0), cur(n + 1, 0);
    function<void(int)> dfs = [&](int u) {
        vis[u] = 1;
        for (auto [v, id] : g[u]) {
            if (vis[v]) continue;
            dfs (v);
            if (cur[v] == 0 && Y < k) { 
                Y -= cur[u] + cur[v];
                cur[u] ^= 1; cur[v] ^= 1;
                Y += cur[u] + cur[v];
                ans.push_back(id);
            }
        }
    };

    for (int i = 1; i <= n; i++) 
        if (!vis[i]) dfs(i);
    
    if (Y != k) cout << "No" << endl;
    else {
        cout << "Yes" << endl;
        cout << ans.size() << endl;
        for (auto x : ans) cout << x << " ";
        cout << endl;
    }
    return 0;
}

G - Sugoroku 5

Question

有一个棋盘游戏，其中有 $N + 1$ 个方格：方格 $0$ 、方格 $1$ 、方格 $\dots$ 和方格 $N$ 。
你有一个骰子，它能掷出一个介于 $1$ 和 $K$ 之间的整数，每种结果的概率相等。
您从 $0$ 开始掷骰子。重复下面的操作，直到到达 $N$ 格：

掷骰子。假设 $x$ 是当前方格， $y$ 是掷出的数字，然后移动到方格 $min (N, x + y)$ 。

假设 $P_{i}$ 是经过恰好 $i$ 次操作后到达 $N$ 个方格的概率。计算 $P_{1}, P_{2}, \dots, P_{N}$ % $998244353$

$1 \leq K \leq N \leq 2 \times 10^{5}$

Solution

假设 $F (x)$ 是一次投掷筛子前进 $n$ 格的生成函数

F (x) = \frac{1}{K} \sum_{i = 1}^{K} x^{i}

那么， $k$ 掷完后， $(0 \leq k < N)$ 位于方格的概率表示为 $[x^{k}] F^{n}$ 。 $n$ 掷出之后 $(0 \leq k < N)$ 的概率表示为 $[x^{k}] F^{n}$ 。因此， $a_{n}$ ，即 $n$ 掷出 $(0 \leq n \leq N)$ 后没有达到目标的概率，可以表示为

a_{n} = \sum_{k = 0}^{N - 1} [x^{k}] F^{n}

那么，恰好投掷 $n$ 次后达到目标的概率为 $(1 - a_{n}) - (1 - a_{n - 1}) = a_{n - 1} - a_{n}$

所以只需要枚举 $a_{0}, a_{1}, \dots, a_{n}$ 就可以知道答案

变换一下式子：

\begin{aligned} a_{n} & = \sum_{k = 0}^{N - 1} [x^{k}] F^{n} \\ = [x^{N - 1}] (1 + x + \dots + x^{N - 1}) F^{n} \end{aligned}

考虑按照 $K$ 的大小分类讨论

$K$ 比较大的情况：

\begin{aligned} a_{n} & = [x^{N - 1}] (1 + x + \dots + x^{N - 1}) F^{n} \\ = [x^{N - 1}] (1 + x + \dots + x^{N - 1} + x^{N} + \dots) F^{n} \\ = [x^{N - 1}] \frac{F^{n}}{1 - x} \end{aligned}

F (x) = \frac{1}{K} \sum_{i = 1}^{K} x^{i} = \frac{x (1 - x^{K})}{K (1 - x)}

在上面的表达式中得出

\begin{aligned} a_{n} & = [x^{N - 1}] \frac{x^{n} (1 - x^{K})^{n}}{K^{n} (1 - x)^{n + 1}} \\ = \frac{1}{K^{n}} [x^{N - 1 - n}] (1 - x^{K})^{n} \times \frac{1}{(1 - x)^{n + 1}} \end{aligned}

考虑到 $(1 - x^{K})^{n}$ 只在， $0, K, 2 K, \dots$ 阶项中非零，则可以在 $O (N / K)$ 的时间内求出 $a_{n}$ ， $a_{0} \sim a_{N}$ 的时间复杂度为 $O (N^{2} / K)$

$K$ 比较小的情况

a_{n} = [x^{N - 1}] (1 + x + \dots + x^{N - 1}) F^{n}

先考虑利用分治的方法求 $a_{n}$

#include <iostream>
#include <vector>
using namespace std;

#include "atcoder/convolution.hpp"
#include "atcoder/modint.hpp"
using mint = atcoder::modint998244353;

int N, K;
vector<mint> f; // F = 1/K sum{i=1..K} x^i
vector<mint> a; // (a_0, a_1, ..., a_N)

// input  : l, r, g = (sum{i=0..N-1} x^i) F^l mod x^N
// output : F^{r-l} mod x^N
vector<mint> dc(int l, int r, vector<mint> g) {
  int b = g.size();
  if (l + 1 == r) {
    a[l] = g.back();
    return f;
  }
  int m = (l + r) / 2;
  auto p = dc(l, m, g);
  g = atcoder::convolution(g, p), g.resize(b);
  auto q = dc(m, r, g);
  auto res = atcoder::convolution(p, q);
  if ((int)res.size() > N) res.resize(N);
  return res;
}

int main() {
  cin >> N >> K;
  a.resize(N + 1);
  f.resize(K + 1);
  for (int i = 1; i <= K; i++) f[i] = mint{K}.inv();
  dc(0, N + 1, vector<mint>(N, 1));
  for (int i = 0; i < N; i++) cout << (a[i] - a[i + 1]).val() << "\n";
}

总时间复杂度为 $O (N^{2} \log^{2} N)$

我们发现对于一个递归函数 $d c (l, r, g)$ $g$ 最多乘 $F$ $(r - l + 1)$ 次，那么对于 $g$ 中的小项，对答案没有影响

所以只需要保留最后的 $K \times (r - l + 1) + 1$ 项即可

具体代码为：

  int b = min<int>(g.size(), (r - l - 1) * K + 1);
  g.erase(begin(g), begin(g) + g.size() - b);

这样就能在 $O (N K \log^{2} N)$ 的时间复杂度下解决问题了

分界点取 $K = \sqrt{N} / \log N$

总时间复杂度为 $O (N^{1.5} \log N)$

好像还有 $O (N \log N)$ 的解法，但是我不会www

Code

//https://atcoder.jp/contests/abc345/submissions/51423091
#pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
using LL = long long;
#define endl '\n'
using db = double;
template <class T>
using max_heap = priority_queue<T>;
template <class T>
using min_heap = priority_queue<T, vector<T>, greater<>>;
#include "atcoder/convolution.hpp"
#include "atcoder/modint.hpp"
using mint = atcoder::modint998244353;
int n, K, N;
const int D = ((db)sqrt(2e5) / (db)(log(2e5) / log(2)) + 1);
const int maxn = 3e5;
mint fac[maxn + 1], invfac[maxn + 1];
mint binom(int nn, int mm)  //求组合数 C(mm,nn)
{
	if (nn < mm)
		return 0;
	return fac[nn] * invfac[nn - mm] * invfac[mm];
};
void init()
{
	fac[0] = 1;
	for (int i = 1; i <= maxn; ++i)
		fac[i] = fac[i - 1] * i;
	invfac[maxn] = 1 / fac[maxn];
	for (int i = maxn - 1; i >= 0; --i)
		invfac[i] = invfac[i + 1] * (i + 1);
}
void solve1()
{
	vector<mint> f(n + 1);
	mint tot = 1;
	mint inv = 1, invK = mint{K}.inv();
	for (int i = 1; i <= n; ++i)
	{
		tot *= K;
		mint res = 0;
		inv *= invK;
		if (1LL * i * K < 1LL * n)
		{
			f[i] = 0;
			continue;
		}
		for (int j = 0; j <= i; ++j)
		{
			int sgn = (j % 2 == 0) ? 1 : -1;
			if (1LL * n - 1 - 1LL * j * (K) < 0)
				break;
			res += sgn * binom(i, j) * binom(n - 1 - j * (K), i);
		}
		f[i] = (tot - res) * inv;
	}
	for (int i = n; i >= 1; --i)
		f[i] -= f[i - 1];
	for (int i = 1; i <= n; ++i)
		cout << f[i].val() << endl;
}
vector<mint> a, f;
vector<mint> dc(int l, int r, vector<mint> g)
{
	int b = min<int>(g.size(), (r - l - 1) * K + 1); // 只保留最后 (r - l) * K 个
	g.erase(begin(g), begin(g) + g.size() - b);
	if (l + 1 == r)
	{
		a[l] = g.back();
		return f;
	}
	int m = (l + r) / 2;
	auto p = dc(l, m, g);
	g = atcoder::convolution(g, p), g.resize(b);
	auto q = dc(m, r, g);
	auto res = atcoder::convolution(p, q);
	if ((int)res.size() > N) res.resize(N);
	return res;
}
void solve2()
{
	a.resize(n + 1);
	f.resize(K + 1);
	for (int i = 1; i <= K; i++)
		f[i] = mint{K}.inv();
	dc(0, N + 1, vector<mint>(N, 1));
	for (int i = 0; i < n; i++)
		cout << (a[i] - a[i + 1]).val() << "\n";
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> K;
	N = n;
	init();
	if (K > D)
		solve1();
	else
		solve2();
	return 0;
}